import Node from "./type";
import { btPrint } from "hy-algokit";

class TreeNode<T> extends Node<T> {
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;
}

//二叉搜索树
class BinarySearchTree<T> {
  private root: TreeNode<T> | null = null;

  //递归插入
  private insertNode(root: TreeNode<T>, newNode: TreeNode<T>) {
    if (newNode.value < root.value) {
      //左子树
      if (!root.left) {
        root.left = newNode;
      } else {
        this.insertNode(root.left, newNode);
      }
    } else {
      //右子树
      if (!root.right) {
        root.right = newNode;
      } else {
        this.insertNode(root.right, newNode);
      }
    }
  }

  //插入操作
  insert(value: T) {
    const newNode = new TreeNode<T>(value);

    if (!this.root) {
      //无根节点
      this.root = newNode;
    } else {
      //有根节点
      this.insertNode(this.root, newNode);
    }
  }

  //打印
  print() {
    btPrint(this.root);
  }

  //先序遍历递归
  private preOrderTraverseLoop(root: TreeNode<T> | null) {
    if (root) {
      console.log(root.value);
      this.preOrderTraverseLoop(root.left);
      this.preOrderTraverseLoop(root.right);
    }
  }
  //先序遍历
  preOrderTraverse() {
    this.preOrderTraverseLoop(this.root);
  }

  //中序遍历递归
  private inOrderTraverseLoop(root: TreeNode<T> | null) {
    if (root) {
      this.inOrderTraverseLoop(root.left);
      console.log(root.value);
      this.inOrderTraverseLoop(root.right);
    }
  }
  //中序遍历
  inOrderTraverse() {
    this.inOrderTraverseLoop(this.root);
  }

  //后序遍历递归
  private postTraverseLoop(root: TreeNode<T> | null) {
    if (root) {
      this.postTraverseLoop(root.left);
      this.postTraverseLoop(root.right);
      console.log(root.value);
    }
  }
  //后序遍历
  postOrderTraverse() {
    this.postTraverseLoop(this.root);
  }

  //层序遍历
  levelOrderTraverse() {
    if (!this.root) return;

    //根节点入栈
    const queue: TreeNode<T>[] = [];
    queue.push(this.root);

    //根节点出栈，同时左节点和右节点入栈
    while (queue.length) {
      const node = queue.shift();
      console.log(node?.value);
      node?.left && queue.push(node?.left);
      node?.right && queue.push(node?.right);
    }
  }

  //获取最大值
  getMaxValue(): T | null {
    //一直往右节点找
    if (!this.root) return null;
    let current = this.root;
    while (current && current.right) {
      current = current.right;
    }
    return current.value;
  }

  //获取最小值
  getMinValue(): T | null {
    //一直往左节点找
    if (!this.root) return null;
    let current = this.root;
    while (current && current.left) {
      current = current.left;
    }
    return current.value;
  }

  //searchLoop

  searchLoop = (root: TreeNode<T> | null, value: T): boolean => {
    if (!root) return false;
    if (root.value < value) {
      return this.searchLoop(root.right, value);
    } else if (root.value > value) {
      return this.searchLoop(root.left, value);
    } else {
      return true;
    }
  };

  //搜索元素
  search(value: T): boolean {
    return this.searchLoop(this.root, value);
  }
}

const BSTree = new BinarySearchTree();

BSTree.insert(11);
BSTree.insert(7);
BSTree.insert(15);
BSTree.insert(5);
BSTree.insert(3);
BSTree.insert(9);
BSTree.insert(8);
BSTree.insert(10);
BSTree.insert(13);
BSTree.insert(12);
BSTree.insert(14);
BSTree.insert(20);
BSTree.insert(18);
BSTree.insert(25);
BSTree.insert(6);

//先序遍历
// BSTree.preOrderTraverse();

//中序遍历
// BSTree.inOrderTraverse();

//后序遍历
// BSTree.postOrderTraverse();

//层序遍历
// BSTree.levelOrderTraverse();

//最大值 最小值
console.log(`最大值:${BSTree.getMaxValue()}`, `最小值：${BSTree.getMinValue()}`);

console.log(BSTree.search(35));
console.log(BSTree.search(17));

console.log(BSTree.search(10));
console.log(BSTree.search(6));

BSTree.print();

export {};
